/**
 * 
 */
package org.srini.interview.sample;

import java.util.ArrayList;

/**
 * @author 
 *
 */
public class BSTTools {
	
	public static void main (String args[]) {
		
		ArrayList<Integer> treeValues = new ArrayList<Integer>();
		for (int i = 0; i < 20; i++) {
			//treeValues.add(new Integer((int)Math.round(Math.random())));
			treeValues.add(new Integer( (int) (Math.random() * 100) ) );
		}
		System.out.println("treeValues :" + treeValues.toString());
		TreeNode bstTree = createBST(treeValues);
		printBST(bstTree);
		System.out.println();
		prettyPrintBST(bstTree);
		System.out.println();
		if (validateBST(bstTree)) {
			System.out.println("Valid BST");
		} else {
			System.out.println("Not a BST");
		}
//		LinkedListTools.printLL(bstTree);
		TreeNode linkedList = convertBSTtoLinkedList(bstTree, false);
		LinkedListTools.printLL(linkedList);
	}
		
	
	/**
	 * This method checks first if the node is valid and only if the node is valid
	 * it checks the left and right trees. Advantage is fail fast, if a node is
	 * not valid the sub-tree, need not be traversed.
	 * Another way would be to traverse the entire tree and see if its a sorted list.
	 * @param inputTree
	 * @return
	 */
			
	public static Boolean validateBST (TreeNode inputTree) {
		Boolean isBST = true;
		Boolean isValidNode = true;
		
		if (inputTree != null) {
			if (inputTree.getLeft() != null) {
				isValidNode = inputTree.getLeft().getValue() < inputTree.getValue();
			}
			if (inputTree.getRight() != null) {
				isValidNode = isValidNode && inputTree.getValue() < inputTree.getRight().getValue();
			}
			
			if (isValidNode) {
				isBST = validateBST(inputTree.getLeft()) && validateBST(inputTree.getRight());
			} else {
				isBST = false;
			}
			
		}	
		
		return isBST;
	}
	
	public static TreeNode createBST (ArrayList<Integer> values) {
		
		//TreeNode retBST = new TreeNode(null, null, 0);
		TreeNode retBST = null;
		for (Integer nodeValue : values) {
			retBST = insertBSTNode(retBST, nodeValue);
		}
		return retBST;
	}
	
	
	/**
	 * STILL WORKING ON THIS
	 */
	public static TreeNode createNonBST (ArrayList<Integer> values) {
		
		//TreeNode retBST = new TreeNode(null, null, 0);
		TreeNode retBST = null;
		for (Integer nodeValue : values) {
			retBST = insertBSTNode(retBST, nodeValue);
			System.out.println("retBST :" + retBST + ":");
		}
		return retBST;
	}
	
	
	/**
	 * Method to insert a node in the BST tree. This is using recursion. Algorithm
	 * 1. If Node is null, create new tree with the value at the root and null Left and Right nodes
	 * 2. Else, if value is less than node, then insert into the LeftNode
	 * 3. If value is more than node, then insert into the RightNode
	 * @param bstTree
	 * @param value
	 * @return
	 */
	public static TreeNode insertBSTNode (TreeNode bstTree, int value) {
		if (bstTree == null) {
			bstTree = new TreeNode(null, null, value);
			//return the new bstTree;
		} else {
			if (value < bstTree.getValue()) {
				if (bstTree.getLeft() == null) {
					bstTree.setLeft(new TreeNode(null, null, value));
				} else {
					insertBSTNode(bstTree.getLeft(), value);
				}

/* I'M SO STUPID NOW I KNOW WHY THIS DOES NOT WORK!!				
				TreeNode leftNode = bstTree.getLeft();
				leftNode = insertBSTNode(bstTree.getLeft(), value);
*/
			}
				
			if (value > bstTree.getValue()) {
				if (bstTree.getRight() == null) {
					bstTree.setRight(new TreeNode(null, null, value));
				} else {
					insertBSTNode(bstTree.getRight(), value);
				}
				
/* I'M SO STUPID NOW I KNOW WHY THIS DOES NOT WORK!!				
				TreeNode rightNode = bstTree.getRight();
				rightNode = insertBSTNode(bstTree.getRight(), value);
*/
			}
			if (bstTree.getValue() == value) {
				//return;
			}
		}
		
		return bstTree;
	}
	

	/**
	 * Converts a BST to a Linked list. Algorithm is:
	 * 0. if node is null, return
	 * 1. leftnode = convert (leftNode)
	 * 2. if left node is not null, leftNode.setNext(node);
	 * 3. if right node is not null, node.setNext (rightNode);
	 * 4. rightNode = convert(rightNode); 
	 * @param bst
	 * @return
	 */
	public static TreeNode convertBSTtoLinkedList(TreeNode bst, boolean returnHigh) {
		//System.out.println("BST :" + bst.getValue());
		if (bst != null) {
			if (bst.getLeft() != null) {
				//System.out.println("before BST :" + bst.getValue() + ": Left :" + bst.getLeft().getValue());
				bst.setLeft(convertBSTtoLinkedList(bst.getLeft(), true));
				bst.getLeft().setRight(bst);
				//System.out.println("after BST :" + bst.getValue() + ": Left :" + bst.getLeft().getValue());
			}
			if (bst.getRight() != null) {
				//System.out.println("before BST :" + bst.getValue() + ": Right :" + bst.getRight().getValue());
				bst.setRight(convertBSTtoLinkedList(bst.getRight(), false));
				bst.getRight().setLeft(bst);
				//System.out.println("after BST :" + bst.getValue() + ": Right :" + bst.getRight().getValue());
			}
			
			if (returnHigh) {
				while (bst.getRight() != null) {
					bst = bst.getRight();
				}
			} else {
				while (bst.getLeft() != null) {
					bst = bst.getLeft();
				}
			}
		}
		
		//System.out.println("return BST :" + bst.getValue());
		return bst;
	}
	
	public static void printBST (TreeNode bstTree) {
		if (bstTree != null) {
			printBST(bstTree.getLeft());
			System.out.print(bstTree.getValue());
			System.out.print(", ");
			printBST(bstTree.getRight());
			if (bstTree.getRight() != null) {
				//System.out.print(", ");
				//printBST(bstTree.getRight());
			}
		}
	}

	public static void prettyPrintBST (TreeNode bstTree) {
		if (bstTree != null) {
			prettyPrintBST(bstTree.getLeft());
			if ((bstTree.getLeft() != null) || (bstTree.getRight() != null)) {
				System.out.print(", ");
			}
			System.out.print(bstTree.getValue());
			prettyPrintBST(bstTree.getRight());
		}
	}


}
